<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>20171024</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <p>爆零不谢.</p>
<pre><code>题目名称    分火腿   无聊的会议 班服
时间限制    1s  1s  1s
内存限制    64MB    128MB   128MB
输入文件    hdogs.in    meeting.in  shirt.in
输出文件    hdogs.out   meeting.out shirt.out
测试点个数 10  10  10

测评环境：windows系统
水题，众神轻虐</code></pre>
<h2 id="toc-0">T1</h2>
<pre><code>分火腿
（hdogs.pas/.c/.cpp）
时间限制：1s；内存限制 64MB
题目描述：
小月言要过四岁生日了，她的妈妈为她准备了n根火腿，她想将这些火腿均分给m位小朋友，所以她可能需要切火腿.为了省事，小月言想切最少的刀数，使这n根火腿分成均等的m份.请问最少要切几刀？
输入描述：
第一行一个整数T，表示有T组数据.
接下来T组数据，每组共一行，有两个数字n，m.
输出描述：
每组数据一行，输出最少要切的刀数.
样例输入：
2
2 6
6 2
样例输出：
4
0
数据范围：
100%的数据保证T&lt;=1000；n,m&lt;=2147483647.</code></pre>
<p>入眼数学题，需要将n个火腿均分给m人，考试的时候有想其中会有一个人拿到一些零散的，切碎的操作？？事实是存在这种操作的.</p>
<p>公式：</p>
<p>$$m-gcd(n,m)$$</p>
<p>可以理解为我们先把这些火腿当成一根长的.</p>
<blockquote><p>例如n=2,m=4，需要切两刀，如果是一根长的话，需要切3刀，又因为中间本来就是断的，所以切3-1刀.</p>
<p>例如n=3,m=5，需要切四刀，如果是一根长的话，需要切m-1刀.</p>
<p>又例如n=4,m=2，不需要切，如果是一根长的话，需要切m-1刀，又因为本来就是断的，所以不需要切.</p>
</blockquote>
<p>以上就可以知道其取值范围为 [ 0，m-1 ] 刀.</p>
<p>并且少切的数量与其倍数关系有关，所以：</p>
<p>$$ans=max(m-gcd(n,m),0)$$</p>
<p>考试推了个NB公式，完Wa，不放了.</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt; </span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">;</span>

<span class="kt">int</span> <span class="nf">gcd</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span><span class="k">return</span> <span class="n">y</span><span class="o">?</span><span class="n">gcd</span><span class="p">(</span><span class="n">y</span><span class="p">,</span><span class="n">x</span><span class="o">%</span><span class="n">y</span><span class="p">)</span><span class="o">:</span><span class="n">x</span><span class="p">;}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;hdogs.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;hdogs.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">t</span><span class="p">;</span>
    <span class="n">read</span><span class="p">(</span><span class="n">t</span><span class="p">);</span>
    <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">){</span>
        <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">m</span><span class="p">);</span> 
        <span class="kt">int</span> <span class="n">ss</span><span class="o">=</span><span class="n">gcd</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="n">m</span><span class="p">);</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">m</span><span class="o">-</span><span class="n">ss</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>T2</p>
<pre><code>无聊的会议
（meeting.pas/.c/.cpp）
时间限制：1s；内存限制 128MB
题目描述：
土豪学长作为一名光荣的学生会干部，每天要参加很多无聊的会议。他发现：他开会的会议桌一定是正n边形，n个干部坐在这个多边形顶点上。因为太无聊了，所以他想要数出所有的“完全”等腰三角形——这种等腰三角形的三个顶点一定全是给出n多边形的顶点，且三个顶点上坐的干部性别相同。
土豪学长是土豪，他用1000000000%10的佣金雇用你，让你帮他数。PS：如果两个“完全”等腰三角形三个顶点相同，计算时只算一个。
输入描述：
第一行一个数字T，表示有T组数据。
接下来有T组数据，每组数据共一行。这一行给出一个长度为n的字符串，表示正n边形n个顶点上干部的性别。1为男，0为女。
输出描述：
对于第i组数据：输出”Case i: ans”(不带引号)，ans为“完全”等腰三角形的数量。
样例输入：
5
0001
01
10001
1101010
111010
样例输出：
Case 1: 1
Case 2: 0
Case 3: 1
Case 4: 3
Case 5: 2
数据范围：
40%的数据保证n&lt;=20
100%的数据保证 n&lt;=10^6
所有数据保证T&lt;=10</code></pre>
<p>40分暴力,qaj.dalao写的暴力好妙啊。</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="kt">char</span> <span class="n">S</span><span class="p">[</span><span class="mi">200010</span><span class="p">];</span>
<span class="kt">int</span> <span class="n">n</span><span class="p">,</span><span class="n">f</span><span class="p">[</span><span class="mi">210</span><span class="p">][</span><span class="mi">210</span><span class="p">][</span><span class="mi">210</span><span class="p">],</span><span class="n">s</span><span class="p">[</span><span class="mi">200010</span><span class="p">];</span>

<span class="kr">inline</span> <span class="kt">void</span> <span class="nf">ww</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="kt">int</span> <span class="n">j</span><span class="p">,</span><span class="kt">int</span> <span class="n">k</span><span class="p">)</span>
<span class="p">{</span>
    <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">k</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">][</span><span class="n">k</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">j</span><span class="p">][</span><span class="n">k</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">j</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">t</span><span class="p">;</span>
    <span class="n">read</span><span class="p">(</span><span class="n">t</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">qq</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">qq</span><span class="o">&lt;=</span><span class="n">t</span><span class="p">;</span><span class="n">qq</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">memset</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="k">sizeof</span><span class="p">(</span><span class="n">f</span><span class="p">));</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%s&quot;</span><span class="p">,</span><span class="n">S</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">n</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">S</span><span class="o">+</span><span class="mi">1</span><span class="p">);</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">S</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-</span><span class="sc">&#39;0&#39;</span><span class="p">,</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">]</span><span class="o">=</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
        <span class="kt">int</span> <span class="n">end</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="kt">int</span> <span class="n">pre</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">2</span><span class="p">)</span> <span class="n">pre</span><span class="o">++</span><span class="p">;</span><span class="k">else</span> <span class="n">end</span><span class="o">--</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">pre</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">+</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">])</span><span class="k">continue</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&gt;=</span><span class="n">i</span><span class="o">-</span><span class="n">end</span><span class="p">;</span><span class="n">j</span><span class="o">--</span><span class="p">){</span>
                <span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">i</span><span class="o">+</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">k</span><span class="o">&gt;</span><span class="n">n</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span>
                <span class="kt">int</span> <span class="n">ii</span><span class="o">=</span><span class="n">i</span><span class="o">%</span><span class="n">n</span><span class="p">,</span><span class="n">jj</span><span class="o">=</span><span class="n">j</span><span class="o">%</span><span class="n">n</span><span class="p">,</span><span class="n">kk</span><span class="o">=</span><span class="n">k</span><span class="o">%</span><span class="n">n</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">||</span><span class="n">s</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">||</span><span class="n">f</span><span class="p">[</span><span class="n">ii</span><span class="p">][</span><span class="n">jj</span><span class="p">][</span><span class="n">kk</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span>
                <span class="n">ww</span><span class="p">(</span><span class="n">ii</span><span class="p">,</span><span class="n">jj</span><span class="p">,</span><span class="n">kk</span><span class="p">);</span>
                <span class="n">ans</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="n">pre</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="o">+</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">])</span><span class="k">continue</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&gt;=</span><span class="n">i</span><span class="o">-</span><span class="n">end</span><span class="p">;</span><span class="n">j</span><span class="o">--</span><span class="p">){</span>
                <span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">i</span><span class="o">+</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">k</span><span class="o">&gt;</span><span class="n">n</span><span class="o">*</span><span class="mi">2</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span>
                <span class="kt">int</span> <span class="n">ii</span><span class="o">=</span><span class="n">i</span><span class="o">%</span><span class="n">n</span><span class="p">,</span><span class="n">jj</span><span class="o">=</span><span class="n">j</span><span class="o">%</span><span class="n">n</span><span class="p">,</span><span class="n">kk</span><span class="o">=</span><span class="n">k</span><span class="o">%</span><span class="n">n</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="o">!</span><span class="n">s</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">||!</span><span class="n">s</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">||</span><span class="n">f</span><span class="p">[</span><span class="n">ii</span><span class="p">][</span><span class="n">jj</span><span class="p">][</span><span class="n">kk</span><span class="p">])</span> <span class="k">continue</span><span class="p">;</span>
                <span class="n">ww</span><span class="p">(</span><span class="n">ii</span><span class="p">,</span><span class="n">jj</span><span class="p">,</span><span class="n">kk</span><span class="p">);</span>
                <span class="n">ans</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Case %d: %d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">qq</span><span class="p">,</span><span class="n">ans</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>50分做法（N3方枚举）</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">const</span> <span class="kt">int</span> <span class="n">maxn</span><span class="o">=</span><span class="mi">2000010</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">T</span><span class="p">,</span><span class="n">n</span><span class="p">,</span><span class="n">ans</span><span class="p">,</span><span class="n">sum</span><span class="p">,</span><span class="n">cas</span><span class="p">,</span><span class="n">x</span><span class="p">,</span><span class="n">y</span><span class="p">,</span><span class="n">z</span><span class="p">;</span>
<span class="kt">char</span> <span class="n">s</span><span class="p">[</span><span class="n">maxn</span><span class="p">];</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">T</span><span class="p">);</span>
    <span class="k">while</span><span class="p">(</span><span class="n">T</span><span class="o">--</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%s&quot;</span><span class="p">,</span><span class="n">s</span><span class="p">);</span>
        <span class="n">n</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">s</span><span class="p">);</span><span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">sum</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="o">+</span><span class="n">n</span><span class="p">]</span><span class="o">=</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="o">+</span><span class="n">i</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
                <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span><span class="n">k</span><span class="o">&lt;</span><span class="n">n</span><span class="o">+</span><span class="n">i</span><span class="p">;</span><span class="n">k</span><span class="o">++</span><span class="p">)</span>
                    <span class="k">if</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">s</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">&amp;&amp;</span><span class="n">s</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">==</span><span class="n">s</span><span class="p">[</span><span class="n">k</span><span class="p">]){</span>
                        <span class="n">x</span><span class="o">=</span><span class="n">j</span><span class="o">-</span><span class="n">i</span><span class="p">;</span><span class="n">y</span><span class="o">=</span><span class="n">k</span><span class="o">-</span><span class="n">j</span><span class="p">;</span><span class="n">z</span><span class="o">=</span><span class="n">n</span><span class="o">*</span><span class="mi">2</span><span class="o">-</span><span class="n">k</span><span class="o">+</span><span class="n">i</span><span class="o">-</span><span class="n">n</span><span class="p">;</span>
                        <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">==</span><span class="n">y</span><span class="o">&amp;&amp;</span><span class="n">y</span><span class="o">==</span><span class="n">z</span><span class="p">)</span><span class="n">sum</span><span class="o">++</span><span class="p">;</span>
                        <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">==</span><span class="n">y</span><span class="o">||</span><span class="n">y</span><span class="o">==</span><span class="n">z</span><span class="o">||</span><span class="n">x</span><span class="o">==</span><span class="n">z</span><span class="p">)</span><span class="n">ans</span><span class="o">++</span><span class="p">;</span>
                    <span class="p">}</span>
        <span class="n">ans</span><span class="o">/=</span><span class="mi">3</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">3</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span><span class="n">ans</span><span class="o">+=</span><span class="n">sum</span><span class="o">/</span><span class="mi">3</span><span class="p">;</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Case %d: %d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="o">++</span><span class="n">cas</span><span class="p">,</span><span class="n">ans</span><span class="p">);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>枚举顶点，然后在枚举任一与他颜色不同的底边点（即为多边形上所有与它颜色不同的点的个数O（1）），求出异色边的数量。这样子有一种三角形（顶点与两底边点一个为同色，一个为异色）数了一次，有一种三角形（顶点与两底边点均为异色）数了两次。可以使其都计算两次。</p>
<p>计算顶点与一底边点一个为同色，一个为异色的三角行的个数：枚举两个底端点，保证其颜色不一样。n为奇数时，任意两个点都能形成底边。n为偶数时，奇偶性相同的点能形成底边。异色边都计算了两次，除以2，就是底边异色的个数。即为三角形的个数。</p>
<p>100分做法：</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="cp">#define ll long long</span>
<span class="kt">int</span> <span class="n">T</span><span class="p">,</span><span class="n">n</span><span class="p">;</span>
<span class="kt">char</span> <span class="n">a</span><span class="p">[</span><span class="mi">1000005</span><span class="p">];</span>

<span class="n">ll</span> <span class="nf">calcu</span><span class="p">(){</span>
    <span class="n">ll</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="n">ans</span><span class="o">=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">n</span><span class="o">*</span><span class="p">((</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">);</span>
    <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">3</span><span class="o">==</span><span class="mi">0</span><span class="p">)</span><span class="n">ans</span><span class="o">-=</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span>
    <span class="k">return</span> <span class="n">ans</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">ll</span> <span class="nf">del</span><span class="p">(){</span>
    <span class="n">ll</span> <span class="n">ans</span><span class="p">;</span>
    <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">2</span><span class="o">==</span><span class="mi">1</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">s1</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">s0</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="sc">&#39;0&#39;</span><span class="p">)</span><span class="n">s0</span><span class="o">++</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">s1</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">ans</span><span class="o">=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">s1</span><span class="o">*</span><span class="n">s0</span><span class="o">*</span><span class="mi">3</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">3</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
            <span class="n">s1</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="p">;</span><span class="n">s0</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
                <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="n">a</span><span class="p">[(</span><span class="n">i</span><span class="o">+</span><span class="n">s1</span><span class="p">)</span><span class="o">%</span><span class="n">n</span><span class="p">])</span><span class="n">ans</span><span class="o">--</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="n">a</span><span class="p">[(</span><span class="n">i</span><span class="o">+</span><span class="n">s0</span><span class="p">)</span><span class="o">%</span><span class="n">n</span><span class="p">])</span><span class="n">ans</span><span class="o">--</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">ans</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="k">else</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">s00</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">s01</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">s10</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="n">s11</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="sc">&#39;0&#39;</span><span class="p">)</span><span class="n">s00</span><span class="o">++</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">s01</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">+=</span><span class="mi">2</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="sc">&#39;0&#39;</span><span class="p">)</span><span class="n">s10</span><span class="o">++</span><span class="p">;</span>
            <span class="k">else</span> <span class="n">s11</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">ans</span><span class="o">=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">s00</span><span class="o">*</span><span class="n">s11</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span><span class="n">ans</span><span class="o">+=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">s01</span><span class="o">*</span><span class="n">s10</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span>
        <span class="n">ans</span><span class="o">+=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">s00</span><span class="o">*</span><span class="n">s01</span><span class="o">*</span><span class="mi">4</span><span class="p">;</span><span class="n">ans</span><span class="o">+=</span><span class="p">(</span><span class="n">ll</span><span class="p">)</span><span class="n">s10</span><span class="o">*</span><span class="n">s11</span><span class="o">*</span><span class="mi">4</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">n1</span><span class="p">,</span><span class="n">n2</span><span class="p">;</span>
        <span class="n">n1</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="n">a</span><span class="p">[(</span><span class="n">i</span><span class="o">+</span><span class="n">n1</span><span class="p">)</span><span class="o">%</span><span class="n">n</span><span class="p">])</span><span class="n">ans</span><span class="o">--</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">n</span><span class="o">%</span><span class="mi">3</span><span class="o">==</span><span class="mi">0</span><span class="p">){</span>
            <span class="kt">int</span> <span class="n">s1</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="p">,</span><span class="n">s0</span><span class="o">=</span><span class="n">n</span><span class="o">/</span><span class="mi">3</span><span class="o">*</span><span class="mi">2</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
                <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="n">a</span><span class="p">[(</span><span class="n">i</span><span class="o">+</span><span class="n">s1</span><span class="p">)</span><span class="o">%</span><span class="n">n</span><span class="p">])</span><span class="n">ans</span><span class="o">--</span><span class="p">;</span>
                <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">!=</span><span class="n">a</span><span class="p">[(</span><span class="n">i</span><span class="o">+</span><span class="n">s0</span><span class="p">)</span><span class="o">%</span><span class="n">n</span><span class="p">])</span><span class="n">ans</span><span class="o">--</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">ans</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;meeting.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">T</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">Case</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">T</span><span class="o">--</span><span class="p">){</span>
        <span class="n">Case</span><span class="o">++</span><span class="p">;</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%s&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">a</span><span class="p">);</span>
        <span class="n">n</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">a</span><span class="p">);</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Case %d: %I64d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">Case</span><span class="p">,</span><span class="n">calcu</span><span class="p">()</span><span class="o">-</span><span class="n">del</span><span class="p">());</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>T3</p>
<pre><code>班服
 (shirt.pas/.c/.cpp)

时间限制：1s；内存限制 128MB

题目描述：

要开运动会了，神犇学校的n个班级要选班服，班服共有100种样式，编号1~100。现在每个班都挑出了一些样式待选，每个班最多有100个待选的样式。要求每个班最终选定一种样式作为班服，且该班的样式不能与其他班级的相同，求所有可能方案的总数，由于方案总数可能很大，所以要求输出mod 1000000007后的答案。

输入描述：

共有T组数据。

对于每组数据，第一行为一个整数n，表示有n个班级。

2~n+1行，每行有最多100个数字，表示第i-1班待选班服的编号。

输出描述：

对于每组数据，输出方案总数 mod 1000000007后的答案。

样例输入：

2

3
5 100 1
2
5 100

2
3 5
8 100

样例输出：

4
4

数据范围：

对于30%的数据，1&lt;=T&lt;=3, 1&lt;=n&lt;=3，每班待选样式不超过10种。

对于50%的数据，1&lt;=T&lt;=5, 1&lt;=n&lt;=5，每班待选样式不超过50种。

对于100%的数据，1&lt;=T&lt;=10, 1&lt;=n&lt;=10，每班待选样式不超过100种。</code></pre>
<p>考试的时候看了一下数据范围，n&lt;=10，给我一种状压dp的感觉，但是dp刷的太少了，这种操作显然是不存在的，所以就GG了，据说爆搜50?!?!?!</p>
<p>我们对已选择的班级进行状态压缩，用f[i][j]表示前i中班服到达状态j的方案书，转移的话。。如果不选第i种班服的话，那么f[i][j]=f[i-1][j]，如果要选，那么一定可以在可选班服列表中有第i种班服的班级中选择。</p>
<p>条件状态j中有第k个班，并且k班可以选第i中班服</p>
<p>满足条件</p>
<p>(f[i][j]+=dp[i-1][j^(1&lt;&lt;k-1)])%=Mod;</p>
<p>最后答案在第100件衣服，最大的班级编号里面。</p>
<p>我们用二进制来表示状态的话，一共10个班，所以一共2^10=1024种状态，一共100件衣服，再枚举一个k，所以总的时间为</p>
<p>O（1024 <em> 100 </em> 100 * 10）最后这个10是t</p>
<p>近似为100000000</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;ctime&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="k">const</span> <span class="kt">int</span> <span class="n">lxn</span><span class="o">=</span><span class="mi">1000000007</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">t</span><span class="p">,</span><span class="n">f</span><span class="p">[</span><span class="mi">101</span><span class="p">][</span><span class="mi">1025</span><span class="p">],</span><span class="n">tot</span><span class="p">,</span><span class="n">a</span><span class="p">[</span><span class="mi">15</span><span class="p">][</span><span class="mi">105</span><span class="p">],</span><span class="n">n</span><span class="p">,</span><span class="n">cnt</span><span class="p">[</span><span class="mi">17</span><span class="p">],</span><span class="n">bin</span><span class="p">[</span><span class="mi">16</span><span class="p">];</span>

<span class="kt">void</span> <span class="nf">dp</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">f</span><span class="p">[</span><span class="mi">0</span><span class="p">][</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="mi">100</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;=</span><span class="n">tot</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
            <span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="p">];</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">k</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">k</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">k</span><span class="o">++</span><span class="p">)</span>
                <span class="k">if</span><span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="n">k</span><span class="p">][</span><span class="n">i</span><span class="p">]</span><span class="o">&amp;&amp;</span><span class="p">(</span><span class="n">j</span><span class="o">&amp;</span><span class="n">bin</span><span class="p">[</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">]))</span>
                    <span class="p">(</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">]</span><span class="o">+=</span><span class="n">f</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">][</span><span class="n">j</span><span class="o">^</span><span class="n">bin</span><span class="p">[</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">]])</span><span class="o">%=</span><span class="n">lxn</span><span class="p">;</span>
        <span class="p">}</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">bin</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="mi">10</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="n">bin</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">bin</span><span class="p">[</span><span class="n">i</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">;</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;shirt.in&quot;</span><span class="p">,</span><span class="s">&quot;r&quot;</span><span class="p">,</span><span class="n">stdin</span><span class="p">);</span>
    <span class="n">freopen</span><span class="p">(</span><span class="s">&quot;shirt.out&quot;</span><span class="p">,</span><span class="s">&quot;w&quot;</span><span class="p">,</span><span class="n">stdout</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">t</span><span class="p">;</span>
    <span class="n">read</span><span class="p">(</span><span class="n">t</span><span class="p">);</span>  
    <span class="k">while</span><span class="p">(</span><span class="n">t</span><span class="o">--</span><span class="p">){</span>
        <span class="n">memset</span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="mi">0</span><span class="p">,</span><span class="k">sizeof</span><span class="p">(</span><span class="n">a</span><span class="p">));</span>
        <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">);</span><span class="n">tot</span><span class="o">=</span><span class="n">bin</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="kt">int</span> <span class="n">x</span><span class="p">;</span><span class="kt">char</span> <span class="n">c</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
            <span class="k">while</span><span class="p">(</span><span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">x</span><span class="p">)){</span>
                <span class="o">++</span><span class="n">cnt</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="n">a</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">x</span><span class="p">]</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span>
                <span class="n">c</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span><span class="k">if</span><span class="p">(</span><span class="n">c</span><span class="o">==</span><span class="sc">&#39;\n&#39;</span><span class="p">)</span> <span class="k">break</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="n">dp</span><span class="p">();</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">f</span><span class="p">[</span><span class="mi">100</span><span class="p">][</span><span class="n">tot</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="mi">0</span> <span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>By:Wahacer</p>
<p>2017.10.24</p>
<p>21.26</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>